The A* algorithm is a heuristic search most often used for finding shortest-path routes. If the heuristic guarantees a lower bound on the costs of any node below, then this can be used to prune whole branches where the heurisic exceeds the current best solution. That is, it can be seen as heuristic version of branch and bound. Often the raw heuristic is about the path beyond the node, for example the Euclidean distance (as the crow flies) to the target location in geographic shortest path search, in which case the distance along the path to the node has to be added to the raw heuristic to create a total path lower bound. The heauristic can also be used to guide the next node to explore in a variant of hill climbing.
Defined on pages 72, 74
Used on pages 72, 74, 81, 349
Also known as A* algorithm
Using the A*algorithm